package com.ry.day1129;

import java.util.Stack;

public class LC915 {


      static class TreeNode {
          public int val;
          public TreeNode left, right;
          public TreeNode(int val) {
             this.val = val;
              this.left = this.right = null;
          }
      }


    static class Solution {
        /**
         * @param root: the given BST
         * @param p: the given node
         * @return: the in-order predecessor of the given node in the BST
         */
        public TreeNode inorderPredecessor(TreeNode root, TreeNode p) {
            Stack<TreeNode> s = new Stack<>();
            TreeNode pre = null;
            while (!s.isEmpty() || root!=null){
                while (root!=null){
                    s.add(root);
                    root= root.left;
                }

                root = s.pop();

                if(pre!=null && root ==p){
                    return pre;
                }

                pre= root;
                root= root.right;
            }

            return null;
        }
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
915 · BST的中序前驱节点
算法
中等
通过率
58%

题目
题解42
笔记
讨论99+
排名
记录
描述
给出一棵二叉搜索树以及其中的一个节点，找到这个节点在这棵树中的中序前驱节点。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


如果给出的节点在树中没有中序前驱节点， 返回 null。

样例
样例1

输入: root = {2,1,3}, p = 1
输出: null
样例2

输入: root = {2,1}, p = 2
输出: 1
标签
企业
Facebook
Microsoft
相关题目

67
二叉树的中序遍历
简单

86
二叉查找树迭代器
困难

448
二叉查找树的中序后继
中等
推荐课程

Twitter 后端系统 - Python 项目实战
从0项目经验到深度后端项目操盘，FB架构师万行代码还原真实开发环境，14周简历镀金
43/77
已开启智能提示
发起考试
30 分 00 秒
12345678910111213141516171819202122
    }
}
控制台
历史提交

 */
